An official website of the United States government
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
In numerical linear algebra, a well-established practice is to choose a norm that exploits the structure of the problem at hand to optimise accuracy or computational complexity. In numerical polynomial algebra, a single norm (attributed to Weyl) dominates the literature. This article initiates the use of L_p norms. This classical idea yields strong improvements in the analysis of the number of steps performed by numerous iterative algorithms. In particular, we exhibit three algorithms where, despite the complexity of computing L_{infinity } norm the use L_p norms substantially reduces computational complexity: a subdivision-based algorithm in real algebraic geometry for computing the homology of semialgebraic sets, a well-known meshing algorithm in computational geometry and the computation of zeros of systems of complex quadratic polynomials (a particular case of Smale’s 17th problem).more » « less
-
We consider the sensitivity of real zeros of structured polynomial systems to pertubations of their coefficients. In particular, we provide explicit estimates for condition numbers of structured random real polynomial systems and extend these estimates to the smoothed analysis setting.more » « less
-
We consider the sensitivity of real roots of polynomial systems with respect to perturbations of the coefficients. In particular --- for a version of the condition number defined by Cucker and used later by Cucker, Krick, Malajovich, and Wschebor --- we establish new probabilistic estimates that allow a much broader family of measures than considered earlier. We also generalize further by allowing over-determined systems. In Part II, we study smoothed complexity and how sparsity (in the sense of restricting which terms can appear) can help further improve earlier condition number estimates.more » « less
